package com.summli.basic.class02;

import java.util.Stack;

/**
 *实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
 *
 * 1）pop、push、getMin操作的时间复杂度都是 O(1)。
 *
 * 2）设计的栈类型可以使用现成的栈结构。
 */
public class Code05_GetMinStack {
    public static class MyStack1{
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1() {
            stackData = new Stack<>();
            stackMin = new Stack<>();
        }

        public void push(int newNum) {
            if(!stackData.isEmpty() && stackData.peek() < newNum){
                stackMin.push(stackData.peek());
            }else{
                stackMin.push(newNum);
            }
            stackData.push(newNum);
        }

        public int pop(){
            if(stackData.isEmpty()){
                throw new RuntimeException("stack is empty!");
            }
            stackMin.pop();
            return stackData.pop();
        }

        public int getmin(){
            if(stackMin.isEmpty()){
                throw new RuntimeException("stack is empty!");
            }
            return stackMin.peek();
        }
    }

    public static void main(String[] args) {
        MyStack1 stack1 = new MyStack1();
        stack1.push(3);
        System.out.println(stack1.getmin());
        stack1.push(4);
        System.out.println(stack1.getmin());
        stack1.push(1);
        System.out.println(stack1.getmin());
        System.out.println(stack1.pop());
        System.out.println(stack1.getmin());

        System.out.println("=============");

        MyStack1 stack2 = new MyStack1();
        stack2.push(3);
        System.out.println(stack2.getmin());
        stack2.push(4);
        System.out.println(stack2.getmin());
        stack2.push(1);
        System.out.println(stack2.getmin());
        System.out.println(stack2.pop());
        System.out.println(stack2.getmin());
    }

}
